package com.neuedu.linkedlist;

import java.util.Iterator;

/**
 * 链表：无非就是判断
 *         1.是否是头节点
 *         2.是否为null
 *         3.是否索引越界
 *         4.添加删除，找上一个节点和下一个节点
 *         5.找指定节点，遍历到index==i
 */
public class DoublyLinkedListSentinel implements Iterable<Integer>{//环形双向链表(环，不会存在越界问题)
    //使用Iterator可以方便地**遍历一个集合**的所有元素，而不需要关心集合内部的具体实现细节。

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node cur = sentinel.next;
            @Override
            public boolean hasNext() {
                return cur!=sentinel;
            }

            @Override
            public Integer next() {
                Integer value = cur.value;
                cur = cur.next;
                return value;
            }
        };
    }

    //iterator,addFirst,addLast removeFirst removeLast removeByValue findNodeByValue
    static class Node{
        private Node pre;
        private Node next;
        private Integer value;

        public Node(Node pre, Node next, Integer value) {
            this.pre = pre;
            this.next = next;
            this.value = value;
        }
    }
    private final Node sentinel = new Node(null,null,-1);

    public DoublyLinkedListSentinel() {
        sentinel.next = sentinel;
        sentinel.pre = sentinel;
    }

    public void addFirst(int value){
        Node next = sentinel.next;
        Node cur = new Node(sentinel, next, value);//当前添加的节点
        sentinel.next = cur;
        next.pre = cur;
    }

    public void addLast(int value){
        Node pre = sentinel.pre;
        if (pre == sentinel){//证明链表无数据，添加到最后一个即添加到第一个
            addFirst(value);
            return;
        }
        Node cur = new Node(pre, sentinel, value);
        pre.next = cur;
        sentinel.pre = cur;
    }

    public void removeFirst(){
        Node removed = sentinel.next;
        if (removed == sentinel){//没有移除的元素
            throw new IllegalArgumentException("非法");
        }
        Node next = sentinel.next.next;
        sentinel.next = next;
        next.pre = sentinel;
    }

    public void removeLast(){
        Node removed = sentinel.pre;
        if (removed == sentinel){//没有移除的元素
            throw new IllegalArgumentException("非法");
        }
        Node pre = removed.pre;
        pre.next = sentinel;
        sentinel.pre = pre;
    }

    public Node findNode(int index){
        int i = 0;
        for (Node cur = sentinel.next; cur!= sentinel ; cur = cur.next , i++){
            if (index == i){
                return cur;
            }
        }
        return null;
    }

    /**
     * 通过值删除
     * @param value
     */
    public void removeByValue(int value){
        int i = 0;
        for (Node cur = sentinel.next ; cur != sentinel ; cur = cur.next , i++){
            if (value == cur.value){
                Node removed = findNode(i);
                if (removed == null){
                    throw illegalIndex(i);
                }
                Node pre = removed.pre;
                Node next = removed.next;
                pre.next = next;
                next.pre = pre;
            }
        }
    }

    public Node findNodeByValue(int value){
        int i = 0;
        for (Node cur = sentinel.next; cur != sentinel ; cur = cur.next , i++){
            if (cur.value == value){
                return findNode(i);
            }
        }
        return null;
    }

    public IllegalArgumentException illegalIndex(int index){
        throw new IllegalArgumentException(String.format("索引[%d],不合法%n",index));
    }
}
